%%
%实现算术编码和解码

%%
% 输入字典：字母letters和概率possible
clear;clc;
letters=input('请输入字典中存在的字母:\n');
possible=input('请输入字母对应的概率:\n');

%% 
% 输入需要进行编码和解码的sequence
sequence=input('请输入需要进行编码和解码的序列:\n','s');

%%
% 累加概率possiblef相当于将前面的possible累加起来，比如possible是0.1 0.2 0.3则possiblef是0.1 0.3 0.6
possiblef=zeros(length(possible));
possiblef(1)=possible(1);
for i=2:length(possible)
    possiblef(i)=possiblef(i-1)+possible(i);
end

% 获得编码区间的变化
lowe=0.0;
highe=1.0;
ranges=[];
for i=1:length(sequence)
    letter=sequence(i);
    [highe,lowe]=findrange(letters,possiblef,letter,highe,lowe);
    ranges=[ranges;lowe,highe];
end

%%
% 得到最短的二进制串
binaryStr=[];
i=1;
binarySum=0;
while(true)
    if (binarySum+2^(-i))>=highe
        binaryStr(i)=0;
    elseif (binarySum+2^(-i))>=lowe
            binaryStr(i)=1;
            binarySum=binarySum+2^(-i);
            break;
    else
        binaryStr(i)=1;
        binarySum=binarySum+2^(-i);
    end
    i=i+1;
end

%%
% 输出最短的二进制串和其所对应的十进制数
binaryStr_out=num2str(binaryStr);
binaryStr_out=replace(binaryStr_out,' ','');
fprintf('\n');
disp('二进制编码：');
disp(binaryStr_out);
disp('对应的是十进制数：')
formatSpec = '%.20f';
binarySum_out=num2str(binarySum,formatSpec);
disp(binarySum_out);

%%
% 解码
% 前提：用到了，书上p76假设编码器和译码器都知道序列的长度，否则不知道啥时候结束迭代
decoderSeq='';
highd=1;
lowd=0;
for i=1:length(sequence)
    [highd,lowd,letter]=decodeSeq(letters,possiblef,highd,lowd,binarySum);
    decoderSeq(i)=letter;
end
disp('输出解码的结果:');
disp(decoderSeq);

%%
% 自动比对原始串和解码串的差别,
% 使用前提：
try
    if sum(decoderSeq==sequence)==length(sequence)
        disp('原始序列/字符串和解码得到的序列/字符串不同字符个数：0,成功！');
    else
        disp(['原始序列/字符串和解码得到的序列/字符串不同字符个数：',num2str(length(sequence)-sum(decoderSeq==sequence)),',fail!']);
    end
catch
    disp('原串和译码串不一样长，比对部分暂时失效');
end

%%
% 第二种输入格式，验收测试的输入说明：
% 字典
% ['A','B','C','D']
% [0.1,0.4,0.2,0.3]
% 待编码的字符串
% CADACDB
